A data communication device, such as a router, usually includes a control plane and a data plane. The control plane is responsible for functions such as routing information collection, routing computation, device management and network management agent. The data plane is also referred to as service plane or forwarding plane and it is responsible for functions such as network flow receiving, path selecting, sending and special service processing.
During the practical forwarding of an IP service, the control plane collects various routing information from other devices via a protocol packet, screens the collected various routing information, and establishes an optimum path information base, then forms a fast forwarding table (FIB) and issues the FIB to the data plane. The FIB is equivalent to a routing map for fast lookup, which is the basis for the data plane to forward information. For all the IP services on the network, a next station to the destination is determined by looking up the FIB via the data plane. Therefore, the FIB is a key data structure for the data plane of the data communication device. The quality of this FIB model would directly influence forwarding efficiency and design complexity of the data plane, thereby influencing performance and reliability of the data communication device.
The FIB is usually looked up according to a destination IP address of an IP packet to be forwarded, and main information looked up is information of a next hop device, for example, the IP address and outgoing interface of the next hop, etc.
A typical FIB model in the prior art is a unified table model. FIG. 1 is a schematic diagram of this model. In this model, a prefix corresponds to a Next Hop Array, and a Next Hop Array may include a plurality of equivalent routings. A load sharing relationship exists between these equivalent routings and the flow of looking up the routing is shared by the plurality of equivalent routings via a special algorithm.
The above prefix refers to an IP address comprising a subnet mask. For example, the prefix may be 1.1.1.1/24; in other words, the IP address is 1.1.1.1 and the subnet mask is 24. Because the lookup of the FIB employs a principle of Longest Prefix Matching. Therefore, an IP packet with the destination IP address of 1.1.1.* corresponds to the same Next Hop Array.
A characteristic of the unified table model lies in that each prefix corresponds to a Next Hop Array, and if a next hop exists in the Next Hop Arrays of a plurality of prefixes, the next hop has several copies at the same time, for example, NextHop1 and NextHop3 as shown in FIG. 1. Therefore, in this model, if a prefix is matched, the Next Hop Array corresponding to the prefix may be obtained at once, without the need to look up other tables.
The above unified table model has the following disadvantages.
1) The space occupied is large. Because the number of prefixes of the present backbone router may reach above 200 thousand, the number of next hops is usually tens to more than one hundred. Therefore, in this model, the content of the same next hop may be copied for tens of thousands of times, and a very large storage space needs to be occupied.
2) The updating speed is low. Updating speed of routing is a key index for measuring a communication device. Because in this model the same next hop has many copies, when a failure occurs in the next hop, the routing protocol needs to spend a long time in deleting all the information of the next hop. As a result, communication traffic between the control plane and the data plane will be increased greatly, sending and receiving other data will be influenced, and the number of lost packets will be increased. During this time period, all the packets that pass through this path might continue to be transmitted on the wrong routing because the routing is not refreshed in time, so that the packets may be discarded. Similarly, when a next hop recovers from a failure, all the related table entries of the next hop will be added again, and this will also cause the communication traffic between the control plane and the data plane to be increased greatly.
Another typical FIB model in the prior art is a scatter table model. This model is put forward by Network Processing Forum (NPF) during 2003 to 2004. A schematic diagram of this model is as shown in FIG. 2.
In the scatter table model, the same Next Hop Array is kept in only one copy in a memory, and a next hop ID structure is added to a corresponding table entry in each prefix. This structure is merely a pointer, which occupies a very little space. A many-to-one correspondence exists between the prefix and the Next Hop Array. In this model, because a many-to-one correspondence is employed, the consumption of the memory will be decreased greatly. Additionally, during updating, only a next hop array needs to be updated, and the updating speed will be accelerated greatly.
A disadvantage of the above scatter table model lies in that the case where different prefixes may have their own private domains is not considered. In practical applications, when different prefixes correspond to the same next hop or next hop array, some private data, such as an inner layer label of a virtual private network of a Route Prefix, a QoS parameter or autonomous domain number information, needs to be kept respectively for different prefixes in many functions. Then, the data communication device may obtain these private data when a service is forwarded, and it may perform different corresponding processes on different prefixes. In the above scatter table model, such different processes cannot be realized.